package org.example.bitOperation;

import java.lang.reflect.Array;
import java.util.*;
import java.util.concurrent.locks.LockSupport;

/**
 * 力扣 -- 位运算
 * @Author chaigq
 * @Date 2020/11/20 12:44 上午
 * @Version 1.0
 */
public class LeetCodeBitOperation {

    /**
     *   找到最接近目标值的函数值
     *
     *  Winston 构造了一个如上所示的函数 func 。他有一个整数数组 arr 和一个整数 target ，他想找到让 |func(arr, l, r) - target|
     *  最小的 l 和 r 。
     *
     *  请你返回 |func(arr, l, r) - target| 的最小值。
     *  请注意， func 的输入参数 l 和 r 需要满足 0 <= l, r < arr.length 。
     *
     *  示例 1：
     *  输入：arr = [9,12,3,7,15], target = 5
     * 输出：2
     * 解释：所有可能的 [l,r] 数对包括 [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,
     * 2],[1,3],[2,4],[0,3],[1,4],[0,4]]， Winston 得到的相应结果为 [9,12,3,7,15,8,0,3,7,0,0,3,0
     * ,0,0] 。最接近 5 的值是 7 和 3，所以最小差值为 2 。
     *
     *  示例 2：
     *  输入：arr = [1000000,1000000,1000000], target = 1
     * 输出：999999
     * 解释：Winston 输入函数的所有可能 [l,r] 数对得到的函数值都为 1000000 ，所以最小差值为 999999 。
     *
     *  示例 3：
     *  输入：arr = [1,2,4,8,16], target = 0
     * 输出：0
     *
     *  提示：
     *  1 <= arr.length <= 10^5
     *  1 <= arr[i] <= 10^6
     *  0 <= target <= 10^7
     *
     *  Related Topics 位运算 线段树 二分查找
     */
    /**
     * TODO ： 解析
     * 题目给定的函数 func(arr, l, r) 实际上求的是 arr[l] 到 arr[r] 的「按位与之和」，
     * 也就是 arr[l] & arr[l+1] & ... & arr[r-1] & arr[r]。
     *
     * 安位与之和性质：如果我们固定右端点 r，并且从大到小在 [0, r] 的区间内枚举左端点 l，那么这个按位与之和是单调递减的。
     * 这是因为按位与之和具有「结合律」，func(arr, l, r) = arr[l] & func(arr, l+1, r)，
     * 由于按位与本身的性质，a & b 的结果不会大于 a 也不会大于 b，因此 func(arr, l, r) <= func(arr, l+1, r)。
     *
     *
     */
    public int closestToTarget(int[] arr, int target) {
        ArrayList<Integer> list = new ArrayList<>();
        // 将数组中的数放到list集合中,并且对数据进行去重
        for (int i : arr){
            if (list.isEmpty() || i != list.get(list.size() - 1)){
                list.add(i);
            }
        }
        // 将返回结果设置为最大值
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < list.size(); i ++){
            int arrValue = list.get(i);
            for (int j = i; j < list.size(); j ++){
                arrValue &= list.get(j);
                res = Math.min(res, Math.abs(target - arrValue));
                if (arrValue <= target){
                    break;
                }
            }
        }
        return res;
    }

    /**
     * 作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ 编号为 i 的备选人员
     *  people[i] 含有一份该备选人员掌握的技能列表）。
     *
     *  所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。
     *
     *  我们可以用每个人的编号来表示团队中的成员：例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 p
     * eople[3] 的备选人员。
     *
     *  请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按任意顺序返回答案，本题保证答案存在。
     *
     *  示例 1：
     *  输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["
     * nodejs","reactjs"]]
     * 输出：[0,2]
     *
     *  示例 2：
     *  输入：req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people
     *  = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp
     * ","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
     * 输出：[1,2]
     *
     *  提示：
     *  1 <= req_skills.length <= 16
     *  1 <= people.length <= 60
     *  1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
     *  req_skills 和 people[i] 中的元素分别各不相同
     *  req_skills[i][j], people[i][j][k] 都由小写英文字母组成
     *  本题保证「必要团队」一定存在
     *
     *  Related Topics 位运算 动态规划
     */
    // TODO 用二进制来保存状态，这里需要联系背包问题
    // 相的背包问题
    //
    //使用二进制来保存状态
    //
    //举个例子，假设总共4种技能，3个人，技能情况为[1-1-0-0 , 0-0-1-1 , 1-1-1-1 ]
    //初始状态为0-0-0-0, （以下全部是二进制表示）
    //第一个人到来，0-0-0-0 || 1-1-0-0 = 1-1-0-0 dp[1100] = Math.min(dp[1100],dp[0000]+1) = 1;
    //第二个人到来，1-1-0-0 || 0-0-1-1 = 1-1-1-1 dp[1111] = Math.min(dp[1111],dp[1100]+1) = 2;
    //第三个人到来，0-0-0-0 || 1-1-1-1 = 1-1-1-1 dp[1111] = Math.min(dp[1111],dp[0000]+1) = 1;
    //所以最终使用最少的人为1个
    public static int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        int len = req_skills.length;
        // Math.pow 返回2的len次幂
        int length = (int)Math.pow(2,len);
        List<Integer>[] dp = new ArrayList[length];

        Map<String, Integer> map = new HashMap<>();
        // 将技能对应成二进制数
        for (int i = 0; i < req_skills.length; i ++){
            map.put(req_skills[i], i);
        }
        // 初始状态
        dp[0] = new ArrayList<>();
        for (int i = 0; i < people.size(); i ++){
            // 获取当前人技能
            List<String> skills = people.get(i);
            // 存放当前人技能集合
            List<Integer> list = new ArrayList<>();
            // 获取当前人的技能二进制,一个人存在多个技能
            for (int j = 0; j < skills.size(); j ++){
                list.add(map.get(skills.get(j)));
            }
            for (int j = skills.size() - 1; j >= 0; j --){
                if (dp[j] != null){
                    int num = j;
                    // 状态叠加，加入当前人技能
                    for (int k = 0; k < list.size(); k ++){
                        num |= 1<<list.get(k);
                    }
                    if (dp[num] == null || dp[num].size() > dp[j].size() + 1){
                        dp[num] = new ArrayList<>(dp[j]);
                        dp[num].add(i);
                    }
                }
            }
        }
        List<Integer> last = dp[length-1];
        int[] res = new int[last.size()];
        for(int i=0 ; i<last.size() ; i++){
            res[i] = last.get(i);
        }
        return res;
    }

    // TODO 状态压缩DP问题
    public static int[] smallestSufficientTeam2(String[] req_skills, List<List<String>> people){
        // TODO 1、// 将 req_skills 里面提到的所有技术，每个技术的名字，使用二进制的方法进行编码，然后将每个人的技能使用二进制的方法编码成一个正整数。
        HashMap<String, Integer> map = new HashMap<>();
        // 将技能放到map集合中
        for (int i = 0; i < req_skills.length; i ++){
            map.put(req_skills[i], i);
        }
        //
        int[] skill = new int[people.size()];
        for (int i = 0; i < skill.length; i ++){
            // 遍历i下标，people的技能
            for (int j = 0; j < people.get(i).size(); j ++){
                // 获取当前i下人的技能，并遍历
                String peopleSkill = people.get(i).get(j);
                // 根据当前人的技能，从map中查找value值（就是获取技能数组中的index下标）
                int value = map.get(peopleSkill);
                // 1 << value : <<表示左移，不分正负数，低位补0；
                // >>表示右移，如果该数为正，则高位补0，若为负数，则高位补1；
                // >>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0
                // &按位与的运算规则是将两边的数转换为二进制位，然后运算最终值，运算规则即(两个为真才为真)1&1=1 , 1&0=0 , 0&1=0 , 0&0=0
                // |按位或和&按位与计算方式都是转换二进制再计算，不同的是运算规则(一个为真即为真)1|0 = 1 , 1|1 = 1 , 0|0 = 0 , 0|1 = 1
                skill[i] |= 1 << value; // 将其转换成二进制存储
            }
        }
        // TODO 2、在完成了这一步之后，接下来就是使用背包问题的类似思想，从内到外进行扩散了。定义 dp[i] 是技能编码状态为 i 的最优解。
        // 那我们要求的结果就是：dp[(1 << req_skills.size()) - 1]。很容易知道 dp[0] = {}。、
        // 之后就是一个一个人的考虑。假设第 k 个人对应的技能编码是 skills[k]，
        // 那么可以知道：如果之前的某个状态满足：在dp[i] 可以使用若干个人的工作量进行完成的情况下，
        // dp[i] 的长度加上 1 小于 dp[i | skills[k]]，或者 dp[i | skills[k]] 没有被添加过，
        // 那么就要将 dp[i | skills[k]] 替换成 dp[i] 这个数组加上 k 在结尾。这里为何要使用按位或运算呢？
        // 因为之前的技能池加上当前的人的技能池的综合的编码方法，正好就是按位或运算。
        //
        int[][] dp = new int[1 << req_skills.length][];
        // 初始状态
        dp[0] = new int[0];
        int maxSize = 0;
        for (int i = 0; i < skill.length; i ++){
            if (skill[i] == 0){
                continue;
            }
            for (int j = 0; j <= maxSize; j ++){
                if (dp[j] != null){
                    int combination = j | skill[i];
                    if (dp[combination] == null || dp[j].length + 1 < dp[combination].length){
                        dp[combination] = Arrays.copyOf(dp[j], dp[j].length + 1);
                        dp[combination][dp[j].length] = i;
                    }
                }
            }
            maxSize |= skill[i];
        }
        return dp[(1 << req_skills.length) - 1];
    }

    /**
     * 根据数字二进制下 1 的数目排序
     *
     * 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
     *  如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
     *  请你返回排序后的数组。
     *
     *  示例 1：
     *  输入：arr = [0,1,2,3,4,5,6,7,8]
     * 输出：[0,1,2,4,8,3,5,6,7]
     * 解释：[0] 是唯一一个有 0 个 1 的数。
     * [1,2,4,8] 都有 1 个 1 。
     * [3,5,6] 有 2 个 1 。
     * [7] 有 3 个 1 。
     * 按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]
     *
     *  示例 2：
     *  输入：arr = [1024,512,256,128,64,32,16,8,4,2,1]
     * 输出：[1,2,4,8,16,32,64,128,256,512,1024]
     * 解释：数组中所有整数二进制下都只有 1 个 1 ，所以你需要按照数值大小将它们排序。
     *
     *  示例 3：
     *  输入：arr = [10000,10000]
     * 输出：[10000,10000]
     *
     *  示例 4：
     *  输入：arr = [2,3,5,7,11,13,17,19]
     * 输出：[2,3,5,17,7,11,13,19]
     *
     *  示例 5：
     *  输入：arr = [10,100,1000,10000]
     * 输出：[10,100,10000,1000]
     *
     *  提示：
     *  1 <= arr.length <= 500
     *  0 <= arr[i] <= 10^4
     *
     *  Related Topics 排序 位运算
     */
    public int[] sortByBits(int[] arr) {
        Integer[] num = new Integer[arr.length];
        for (int i = 0; i < arr.length; i ++){
            num[i] = arr[i];
        }
        Arrays.sort(num, (o1, o2) -> {
            int bitCountA = Integer.bitCount(o1);
            int bitCountB = Integer.bitCount(o2);
            return bitCountA == bitCountB ? o1 - o2 : bitCountA - bitCountB;
        });
        for (int k = 0; k < num.length; k ++){
            arr[k] = num[k];
        }
        return arr;
    }

    /**
     * 子集
     * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
     *  说明：解集不能包含重复的子集。
     *
     *  示例:
     *  输入: nums = [1,2,3]
     * 输出:
     * [
     *   [3],
     *   [1],
     *   [2],
     *   [1,2,3],
     *   [1,3],
     *   [2,3],
     *   [1,2],
     *   []
     * ]
     *  Related Topics 位运算 数组 回溯算法
     */
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        list.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i ++){
            int size = list.size();
            for (int j = 0; j < size; j ++){
                List<Integer> integerList = new ArrayList<>(list.get(j));
                integerList.add(nums[i]);
                list.add(integerList);
            }
        }
        return list;
    }
    // 题解路径：https://leetcode-cn.com/problems/subsets/solution/hui-su-python-dai-ma-by-liweiwei1419/
    // 回溯法-深度优先遍历和广度优先遍历
    // （回溯）深度优先遍历：深度优先遍历的特点我们利用Java集合类的栈Stack先进后出的特点来实现
    // 广度优先遍历：我们利用Java数据结构队列Queue来实现
    public static List<List<Integer>> subsets2(int[] nums) {
        int lenth = nums.length;
        // 结果返回值定义
        List<List<Integer>> res = new ArrayList<>();
        if (lenth == 0) return res;
        // 递归
        Deque<Integer> path = new ArrayDeque<Integer>();
        dfs(nums, lenth, 0, path, res);
        return res;
    }

    /**
     * @param nums 数组
     * @param lenth 数组长度
     * @param index 数组索引
     * @param path 栈（路径）
     * @param res 返回结果集
     */
    private static void dfs(int[] nums, int lenth, int index, Deque<Integer> path, List<List<Integer>> res) {
        // 递归终止条件，此时到达递归的叶子节点
        if (lenth == index) {
            // 深度优先遍历会回到原点
            res.add(new ArrayList<>(path));
            return;
        }
        // 递归逻辑
        // TODO 不选择当前元素，进入下一次递归
        dfs(nums, lenth, index + 1, path, res);
        // 选择当前元素，需要将该元素添加到stack的末尾
        path.addLast(nums[index]);
        // 进入下一层递归，形式上一致，但是path不同
        dfs(nums, lenth, index + 1, path, res);
        // 递归结束后需要将对象进行还原操作,将对象的状态重置
        path.removeLast();
    }

    // TODO 方法二
    public static List<List<Integer>> subsets3(int[] nums) {
        int lenth = nums.length;
        // 结果返回值定义
        List<List<Integer>> res = new ArrayList<>();
        if (lenth == 0) return res;
        // 递归
        Deque<Integer> path = new ArrayDeque<Integer>();
        dfs3(nums, lenth, 0, path, res);
        return res;
    }

    /**
     * @param nums 数组
     * @param lenth 数组长度
     * @param begin 位置下标起点
     * @param path 栈（路径）
     * @param res 返回结果集
     */
    private static void dfs3(int[] nums, int lenth, int begin, Deque<Integer> path, List<List<Integer>> res) {
        // 前序遍历结果集
        res.add(new ArrayList<>(path));
        for (int i = begin; i < lenth; i++) {
            // 递归逻辑
            // 选择当前元素，需要将该元素添加到stack的末尾
            path.addLast(nums[i]);
            // 进入下一层递归，形式上一致，但是path不同
            dfs(nums, lenth, i + 1, path, res);
            // 递归结束后需要将对象进行还原操作,将对象的状态重置
            path.removeLast();
        }
    }

    /**
     * 检查一个字符串是否包含长度为k的二进制子串
     * 给你一个二进制字符串 s 和一个整数 k 。
     *  如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 True ，否则请返回 False 。
     *
     *  示例 1：
     *  输入：s = "00110110", k = 2
     * 输出：true
     * 解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。
     *
     *  示例 2：
     *  输入：s = "00110", k = 2
     * 输出：true
     *
     *  示例 3：
     *  输入：s = "0110", k = 1
     * 输出：true
     * 解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。
     *
     *  示例 4：
     *  输入：s = "0110", k = 2
     * 输出：false
     * 解释：长度为 2 的二进制串 "00" 没有出现在 s 中。
     *
     *  示例 5：
     *  输入：s = "0000000001011100", k = 4
     * 输出：false
     *
     *  提示：
     *  1 <= s.length <= 5 * 10^5
     *  s 中只含 0 和 1 。
     *  1 <= k <= 20
     *
     * Related Topics 位运算 字符串
     */
    // TODO 通过滑动窗口+HashSet 找出所有长度为k的去重后的组合,与2^k比较即可
    public boolean hasAllCodes(String s, int k) {
        int left = 0, right = k;
        int lenth = s.length();
        Set<String> set = new HashSet<>();
        while (right <= lenth){
            set.add(s.substring(left, right));
            left ++;
            right ++;
        }
        if (set.size() == Math.pow(2, k)){
            return true;
        }
        return false;
    }












    public static void main(String[] args) {
//        String[] req_skills = {"java","nodejs","reactjs"};
//        List<List<String>> people = new ArrayList<>();
//        List<String> list = new ArrayList<>();
//        list.add("java");
//        people.add(list);
//
//        list = new ArrayList<>();
//        list.add("nodejs");
//        people.add(list);
//        list = new ArrayList<>();
//
//        list.add("java");
//        list.add("nodejs");
//        people.add(list);
//        smallestSufficientTeam(req_skills, people);

        int[] nums = {1,2,3};
        List<List<Integer>> res = subsets3(nums);
        System.out.println(res);

//        LockSupport
    }

}
